package cumt.oj;

/**
 * @Author Fizz Pu
 * @Date 2020/10/7 下午1:50
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */


import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

/**
 * 题目描述
 *     输入一个可能含有重复字符的字符串，打印出该字符串中所有字符的全排列。
 *
 * 输入
 *
 * 单组测试数据，输入数据是一个长度不超过10个字符的字符串，以逗号结尾。
 *
 * 输出
 * 打印出该字符串中所有字符的全排列。以字典序顺序输出，用空格分隔。
 *
 *
 * 样例输入
 * abc,
 * 样例输出
 * abc acb bac bca cab cba
 */

// 全排列树问题， 采用dfs与回溯


public class OjD {
    public static void main(String[] args) {
         // String str = "abc";
        // new OjD().permuteUnique(str);
        Scanner scanner = new Scanner(System.in);
        String str = scanner.next();
        // 去掉,
        str = str.substring(0,str.length()-1);
        new OjD().permuteUnique(str);
    }

    String res = "";
    public void permuteUnique(String nums) {
        int[] vis = new int[nums.length()];
        int height = 1;
        dfs(nums, height, vis);
    }


    void dfs(String nums, int height, int[] vis){
        if(height > nums.length()){
            System.out.print(res+" ");
        } else{
            // 遍历可行解, 使用visited数组来标记已经使用过的元素
            HashSet<Character> reMoveExtra = new HashSet<>();
            for(int i = 0; i < nums.length(); ++i){
                char element = nums.charAt(i);
                if(vis[i] == 0 && !reMoveExtra.contains(element)){//vis[i] == 0 表示元素还没有使用过
                    reMoveExtra.add(element);
                    res += element;
                    vis[i] = 1; // 现在已经使用过
                    dfs(nums, height + 1, vis); // 回溯到下一层
                    vis[i] = 0; // 退出回溯
                    res = res.substring(0,res.length()-1);// 回溯
                }
            }
        }
    }
}